package LeetCode刷题;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-10-01 14:50
 * @description: Functions of this class is
 * <p>
 * 如果两间"相邻"的房屋在同一晚上被小偷闯入，系统会自动报警。
 * 如果房屋数量大于两间，应该如何计算能够偷窃到的最高总金额呢？对于第 k~(k>2) 间房屋，有两个选项：
 *
 * 1.偷窃第 k 间房屋，那么就不能偷窃第 k−1 间房屋，偷窃总金额为前 k−2 间房屋的最高总金额与第 k 间房屋的金额之和。
 * 2.不偷窃第 k 间房屋，偷窃总金额为前 k-1 间房屋的最高总金额。
 *
 * 决定dp[i]的因素就是第i房间偷还是不偷！！！
 **/
public class No动态规划打家劫舍 {
    public static void main(String args[]) {

        System.out.println(rob(new int[]{2, 7, 9, 3, 1}));
    }

    public static int rob(int[] nums) {
        // 官方题解：
        if (nums.length == 1) {
            return nums[0];
        }
        int ans[] = new int[nums.length];
        ans[0] = nums[0];//第一个房屋的金额就等当前的金额

        ans[1] = Math.max(nums[1], ans[0]);//因为只能偷不相邻的房屋，所以到了这里要判断一下偷哪间屋得到的钱最多
        //第二个房屋的金额等上一个！！！！！！千万别忘了！！！！！
        //！！！！！！千万别忘了！！！！！

        for (int i = 2; i < nums.length; i++) {
            //因为每次不能打劫相邻的房屋，所以遍历到当千房屋所打劫到的最大金额，就等于上一座能打劫的房屋+当前房屋里的金额and相邻的房屋所能打劫到的金额的最大值
            ans[i] = Math.max(ans[i - 2] + nums[i], ans[i - 1]);
        }
        return ans[nums.length - 1];
    }

}